// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

// 题干：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
//      设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
//      注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

// 示例：输入：prices = [3,3,5,0,0,3,1,4]
//      输出：6

// 碎语：画出状态积，看看哪里会交易次数＋1

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    const int INF = 0x3f3f3f3f;
    int maxProfit(vector<int>& prices)
    {
        // 1.状态表示
        // dp[i]表示：第i天结束之后，所能获得的最大利润
        // f[i]][j]表示第i天结束之后，完成了j次交易，此时处于买入状态，的最大利润
        // g[i]][j]表示第i天结束之后，完成了j次交易，此时处于卖出状态，的最大利润
        // 2.状态转移方程
        // f[i][j]=f[i-1][j] , g[i-1][j]-p[i]然后取最大值
        // g[i][j]=g[i-1][j] ，f[i-1][j-1]+p[i]

        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INF));
        auto g = f;
        f[0][0] = -prices[0], g[0][0] = 0;

        for (int i = 1 ; i < n  ; i++){
            for (int j = 0 ; j < 3 ; j++){
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0){
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int ret = 0;
        for (int j = 0 ; j < 3 ; j++){
            ret = max(ret, g[n - 1][j]);
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> prices = {3,3,5,0,0,3,1,4};

    cout << sol.maxProfit(prices) << endl;
    
    return 0;
}